package cn.felord.boot;

import com.sun.deploy.util.StringUtils;

import java.util.*;

public class XiaoMi {



    //二分查找
    private static int binary_search(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                return mid;
            }else if (arr[mid] < target) {
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        return -1;
    }

    //链表反转
    private static ListNode reverse_list(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    //合并两个有序数组
    public static int[] merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1, j = n - 1, k = m + n - 1;
        int[] temp = new int[m + n];
        //把数组num1复制到新的数组里面去操作
        System.arraycopy(nums1, 0, temp, 0, m);
        while (i >= 0 && j >= 0) {
            //从数组尾部开始操作,比较nums1[i]与nums2[j]将较大的放在temp尾部
            temp[k--] = temp[i] < nums2[j] ? nums2[j--] : temp[i--];
        }
        return temp;
    }


    //两数之和
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[]{map.get(complement), i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }



    //快速排序
    public static void quickSort(int[] arr,int i,int j){
        // 定义两个变量记录起始索引和结束索引
        int start = i;
        int end = j;

        if (start>end){
            // 递归出口
            return;
        }

        // 定义基准数为起始索引
        int baserNum = arr[i];

        // 利用循环找到要交换的数字
        while (start != end){
            // end从后往前，找基准数小的
            while (true){
                if(end <= start || arr[end]<baserNum){
                    break;
                }
                end--;
            }
            // star 从前往后，找比基准数大的
            while (true){
                if(end <= start || arr[start] > baserNum){
                    break;
                }
                start++;
            }
            // 此时，start指向了比基准数大的数，end指向了比基准数小的数
            // 然后将start指向的数和end指向的数交换
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }

        // 当start和end指向同一个元素，则上面的循环结束
        //表示已经找到了基准数应存入的位置
        //然后 将这个范围中的第一个数和start(或者end)指向的元素进行交换
        //基准数归位
        int temp = arr[start];
        arr[start] = arr[i];
        arr[i] = temp;

        // 利用递归思想，重复上面步骤
        // 上述将基准数放到了该放的位置，即3 1 2 5 4 6 9 7 10 8
        //确定6左边的范围，重复刚刚所做的事情
        quickSort(arr,i,end-1);
        //确定6右边的范围，重复刚刚所做的事情
        quickSort(arr,start+1,j);
    }


    public static void main(String[] args) {
        int[] nums1 = {1, 2, 3, 4, 5};
        int[] nums2 = {4, 5, 3, 2, 1};
        System.out.println(binary_search(nums1, 5));
        int[] res = merge(nums1, 5, nums2, 5);
        System.out.println(Arrays.toString(res));
        quickSort(nums2, 0, nums1.length-1);
        System.out.println(Arrays.toString(nums2));
    }
}
